import java.lang.reflect.Array;
import java.lang.reflect.Parameter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

import javax.swing.tree.TreeNode;

public class lee {

    public static void main(String[] args) {
        String s = "";
        int n = 10000;
        boolean t;
        for (int i = 0; i < n; i++) {
            s += "hello";
        }
        lee newTest = new lee();
        t = newTest.containsNearbyAlmostDuplicate(new int[] { 1, 1 }, 2, 3);
        System.out.println(t);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int[][] merge(int[][] intervals) {
        // 重写排序函数，比较数组左端点大小(a[0]<a[1]时返回负数，则降序)
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        ArrayList<int[]> merged = new ArrayList<int[]>();
        /**
         * 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后， 那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
         * 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点， 将其置为二者的较大值。
         */
        for (int i = 0; i < intervals.length; ++i) {
            int left = intervals[i][0], right = intervals[i][1];
            // mergeg数组中没有值，或者当前区间的左端点在merged中最后一个区间右端点之后
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < left) {
                merged.add(new int[] { left, right });
            } else {
                // merged.add(merged.size()-1, new
                // int[]{merged.get(merged.size()-1)[0],Math.max(right,
                // merged.get(merged.size()-1)[1])});
                merged.get(merged.size() - 1)[1] = Math.max(right, merged.get(merged.size() - 1)[1]);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    public String largestNumber(int[] nums) {
        int n = nums.length;
        // 转换成包装类，以便传入comparator表达式
        Integer[] numsArr = new Integer[n];
        for (int i = 0; i < n; ++i) {
            numsArr[i] = nums[i];
        }
        // lambda表达式
        Arrays.sort(numsArr, (x, y) -> {
            long x1 = Long.parseLong(x.toString() + y.toString());
            long x2 = Long.parseLong(y.toString() + x.toString());
            return (int) (x2 - x1);
        });
        StringBuilder ret = new StringBuilder();
        for (long num : numsArr) {
            ret.append(num);
        }
        return ret.toString();
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }

    class Trie {
        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int index = ch - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = searchPrefix(word);
            return node != null && node.isEnd;
        }

        private Trie searchPrefix(String prefix) {
            Trie node = this;
            for (int i = 0; i < prefix.length(); i++) {
                char ch = prefix.charAt(i);
                int index = ch - 'a';
                if (node.children[index] == null) {
                    return null;
                }
                node = node.children[index];
            }
            return node;
        }

        public boolean isScramble(String s1, String s2) {
            // dp
            // 递归方程组
            System.out.println("r");
            return true;
            // 不会
        }

        // 递归遍历
        List<List<Integer>> levels = new ArrayList<List<Integer>>();

        public void helper(TreeNode node, int level) {
            if (level == levels.size()) {
                levels.add(new ArrayList<Integer>());
            }
            levels.get(level).add(node.val);
            if (node.left != null) {
                helper(node.left, level + 1);
            }
            if (node.right != null) {
                helper(node.right, level + 1);
            }
        }

        public List<List<Integer>> levelOrder(TreeNode root) {
            if (root == null)
                return levels;
            helper(root, 0);
            return levels;
        }

    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // 维护滑动窗口内的元素的数据结构 TreeSet
        // 支持添加和删除指定元素，内部搜索有序，支持二分查找
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < n; ++i) {
            // ceiling返回元素中大于等于e的最小元素
            // 因为k是>=0的数,所以若是集合中要加入两次重复的数（只会增加一次）且第一隔重复的数没有被删除,则会直接返回true
            Long ceiling = set.ceiling((long) nums[i] - (long) t);
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }

    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; ++i) {
            boolean flag = true;
            for (int j = 0; j < m; ++j) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                return i;
        }
        return -1;
    }

    public int numDecodings(String s) {
        // dp
        // dp[i]记录前i个字符的解码总数
        // dp[0]=0,dp[1]=1
        // dp[i]=dp[i] + dp[i-1] or dp[i] = dp[i] + dp[i-2] #
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && (10 * (s.charAt(i - 2) - '0') + (s.charAt(i - 1) - '0')) <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }

    class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    };

    class Solution {
        Map<Integer, Employee> map = new HashMap<Integer, Employee>();

        public int getImportance(List<Employee> employees, int id) {
            for (Employee employee : employees) {
                map.put(employee.id, employee);
            }
            return dfs(id);
        }

        public int dfs(int id) {
            Employee employee = map.get(id);
            int total = 0;
            List<Integer> subordinates = employee.subordinates;
            for (int subId : subordinates) {
                total += dfs(subId);
            }
            return total;
        }
    }

    public int leastBricks(List<List<Integer>> wall) {
        // 砌墙
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (List<Integer> widths : wall) {
            int n = widths.size();
            int sum = 0;
            for (int i = 0; i < n - 1; ++i) {
                sum += widths.get(i);
                cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
            }
        }
        int maxCnt = 0;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            maxCnt = Math.max(maxCnt, entry.getValue());
        }
        return wall.size() - maxCnt;
    }

    // public List<Integer> largestDivisibleSubset(int[] nums) {
    // // dp
    // // dp[i] 具有nums[i]的集合的最大整除子集answer
    // // dp[0]=1
    // int[] dp = new int[nums.length];
    // dp[0] = 1;
    // int ans = 1;
    // Arrays.sort(nums);
    // for (int i = 1; i < nums.length; ++i) {
    // dp[i] = 1;
    // for (int j = 0; j < i; ++j) {
    // if (nums[i] % nums[j] == 0) {
    // dp[i] = Math.max(dp[i], dp[j] + 1);
    // }
    // }
    // }
    // ans = Math.max(ans, dp[nums.length]);
    // }


    //设dp[i,j,k]表示将[0,i]的房子都涂上颜色,最末尾的第i个房子的颜色为j,并且它属于第k个街区时,需要的最少花费.
    //在进行状态转移时,我们需要考虑[第i-1个房子的颜色],这关系到花费以及街区数量的计算,因此我们还需要对其进行枚举.
    //设第i-1个房子的颜色为j_0,
    // 极大值
    // 选择 Integer.MAX_VALUE / 2 的原因是防止整数相加溢出
    static final int INFTY = Integer.MAX_VALUE / 2;

    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        // 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
        for (int i = 0; i < m; ++i) {
            --houses[i];
        }

        // dp 所有元素初始化为极大值
        int[][][] dp = new int[m][n][target];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                Arrays.fill(dp[i][j], INFTY);
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (houses[i] != -1 && houses[i] != j) {
                    continue;
                }
                
                for (int k = 0; k < target; ++k) {
                    for (int j0 = 0; j0 < n; ++j0) {
                        if (j == j0) {
                            if (i == 0) {
                                if (k == 0) {
                                    dp[i][j][k] = 0;
                                }
                            } else {
                                dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][k]);
                            }
                        } else if (i > 0 && k > 0) {
                            dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j0][k - 1]);
                        }
                    }

                    if (dp[i][j][k] != INFTY && houses[i] == -1) {
                        dp[i][j][k] += cost[i][j];
                    }
                }
            }
        }

        int ans = INFTY;
        for (int j = 0; j < n; ++j) {
            ans = Math.min(ans, dp[m - 1][j][target - 1]);
        }
        return ans == INFTY ? -1 : ans;
    }

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
    
    public int shipWithinDays(int[] weights, int D) {
        // 二分查找转换成判定问题
        //
        int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
        while (left < right) {
            int day = 1;
            int wei = 0;
            int mid = (left + right) / 2;
            for (int weight : weights) {
                if (weight + wei > mid) {
                    ++day;
                    wei = 0;
                }
                wei = wei + weight;
            }
            if (day == D) {
                return mid;
            }
            if (day < D) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return -1;
    }
}
